package com.xk._03真题骗._03栈_队列;

import com.xk._03真题骗._00bean.TreeNode;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/*
 * @description: https://leetcode.cn/problems/maximum-binary-tree/
 * @author: xu
 * @date: 2022/10/30 22:44
 */
public class _654最大二叉树1 {
    /*
    * 给定一个不重复的整数数组nums。最大二叉树可以用下面的算法从 nums 递归地构建:
    *       1.创建一个根节点，其值为 nums 中的最大值。
    *       2.递归地在最大值左边的子数组前缀上构建左子树。
    *       3.递归地在最大值右边的子数组后缀上构建右子树。
    * 返回 nums 构建的 最大二叉树
    * */
    public TreeNode constructMaximumBinaryTree1(int[] nums) {
        if (nums == null) return null;
        return findRoot(nums, 0, nums.length);
    }
    private TreeNode findRoot(int[] nums, int left, int right) {
        if (left == right) return null;
        int maxIdx = left;
        for (int i = left + 1; i < right; i++) {
            if (nums[maxIdx] < nums[i]) maxIdx = i;
        }
        TreeNode root = new TreeNode(nums[maxIdx]);
        root.left = findRoot(nums, left, maxIdx);
        root.right = findRoot(nums, maxIdx + 1, right);
        return root;
    }

    public TreeNode constructMaximumBinaryTree2(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        /*
         * 1.扫描一遍所有元素
         * 2.保持栈从栈底到栈顶是单调递减的
         * */
        int len = nums.length;
        Deque<Integer> stack = new LinkedList<>();
        int[] left = new int[len];
        int[] right = new int[len];
        TreeNode[] trees = new TreeNode[len];
        for (int i = 0; i < len; i++) {
            right[i] = -1;
            trees[i] = new TreeNode(nums[i]);
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]){
                right[stack.pop()] = i;
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        TreeNode root = null;
        for (int i = 0; i < len; i++) {
            if (left[i] == -1 && right[i] == -1) {
                root = trees[i];
                continue;
            }
            if (left[i] == -1) {
                trees[right[i]].left = trees[i];
            } else if (right[i] == -1) {
                trees[left[i]].right = trees[i];
            } else if (nums[left[i]] > nums[right[i]]) {
                trees[right[i]].left = trees[i];
            } else {
                trees[left[i]].right = trees[i];
            }
        }
        return root;
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        /*
         * 1.扫描一遍所有元素
         * 2.保持栈从栈底到栈顶是单调递减的
         * */
        int len = nums.length;
        Deque<Integer> stack = new LinkedList<>();
        TreeNode[] trees = new TreeNode[len];
        for (int i = 0; i < len; i++) {
            trees[i] = new TreeNode(nums[i]);
            while (!stack.isEmpty() && nums[i] > nums[stack.peekLast()]){
                trees[i].left = trees[stack.removeLast()];
            }
            if (!stack.isEmpty()) {
                trees[stack.peekLast()].right = trees[i];
            }
            stack.offerLast(i);
        }
        return trees[stack.peekFirst()];
    }


    /*
    * 题目变种：
    *   返回一个数组，数组里面存着每个节点的父节点的索引（如果没有父节点，就存-1）
    *   索引：0  1  2  3  4  5
    *   数组：3  2  1  6  0  5
    *   返回：3  0  1 -1  5  3
    *
    *       ┌───6───┐
    *       │       │
    *       3─┐   ┌─5
    *         │   │
    *         2─┐ 0
    *           │
    *           1
    * 思路：单调递减栈
    * */
    public int[] parentIndexes(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        /*
        * 1.扫描一遍所有元素
        * 2.保持栈从栈底到栈顶是单调递减的
        * */
        int len = nums.length;
        Deque<Integer> stack = new LinkedList<>();
        int[] left = new int[len];
        int[] right = new int[len];
        for (int i = 0; i < len; i++) {
            right[i] = -1;
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]){
                right[stack.pop()] = i;
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        int[] parentIdxes = new int[len];
        for (int i = 0; i < len; i++) {
            if (left[i] == -1 && right[i] == -1) {
                parentIdxes[i] = -1;
                continue;
            }
            if (left[i] == -1) {
                parentIdxes[i] = right[i];
            } else if (right[i] == -1) {
                parentIdxes[i] = left[i];
            } else if (nums[left[i]] > nums[right[i]]) {
                parentIdxes[i] = right[i];
            } else {
                parentIdxes[i] = left[i];
            }
        }
        return parentIdxes;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3,2,1,6,0,5};
        int[] ints = new _654最大二叉树1().parentIndexes(nums);
        System.out.println(Arrays.toString(ints));
    }
}

